#include <stdio.h>
#include <stdlib.h>

// 定义单链表节点
typedef struct ListNode {
	int val;
	struct ListNode *next;
} ListNode;

// 创建新节点
ListNode* createNode(int val) {
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	newNode->val = val;
	newNode->next = NULL;
	return newNode;
}

// 打印链表
void printList(ListNode* head) {
	ListNode* curr = head;
	while (curr) {
		printf("%d ", curr->val);
		curr = curr->next;
	}
	printf("\n");
}

// 合并两个递增链表为一个递减链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
	ListNode* dummy = createNode(0);  // 创建一个虚拟头节点
	ListNode* curr = dummy;
	
	// 当两个链表都不为空时
	while (l1 && l2) {
		// 如果 l1 的值大于 l2 的值
		if (l1->val > l2->val) {
			curr->next = l1;  // 将 l1 节点连接到结果链表
			l1 = l1->next;  // 移动 l1 指针
		} else {
			curr->next = l2;  // 将 l2 节点连接到结果链表
			l2 = l2->next;  // 移动 l2 指针
		}
		curr = curr->next;  // 移动结果链表指针
	}
	
	// 如果 l1 还有剩余节点，连接到结果链表
	if (l1) {
		curr->next = l1;
	}
	// 如果 l2 还有剩余节点，连接到结果链表
	if (l2) {
		curr->next = l2;
	}
	
	ListNode* newHead = dummy->next;  // 获取合并后的头节点
	free(dummy);  // 释放虚拟头节点
	
	// 反转合并后的链表
	ListNode* prev = NULL;
	curr = newHead;
	while (curr) {
		ListNode* nextTemp = curr->next;
		curr->next = prev;
		prev = curr;
		curr = nextTemp;
	}
	
	return prev;  // 返回反转后的头节点
}

int main() {
	// 构建第一个递增链表
	ListNode* l1 = createNode(1);
	l1->next = createNode(3);
	l1->next->next = createNode(5);
	
	// 构建第二个递增链表
	ListNode* l2 = createNode(2);
	l2->next = createNode(4);
	l2->next->next = createNode(6);
	
	ListNode* mergedList = mergeTwoLists(l1, l2);
	
	printf("合并后的递减链表: ");
	printList(mergedList);
	
	// 释放链表内存
	ListNode* temp;
	while (mergedList) {
		temp = mergedList;
		mergedList = mergedList->next;
		free(temp);
	}
	
	return 0;
}
